1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<utility>
using namespace std;
inline long long read(){
long long x=0;int w=0;char c=getchar();
while(!isdigit(c)) w|=c=='-',c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=1e5+10;
int n,q;
int ecnt=1,head[maxn],to[maxn<<1],nxt[maxn<<1],go[maxn];
long long W,w[maxn],dis[maxn];
inline void addedge(){
int a=read(),b=read();
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;
w[ecnt>>1]=read();
}
int dep[maxn],fa[maxn],top[maxn],siz[maxn],son[maxn],dfn[maxn],id[maxn];
void dfs1(int x,int f){
fa[x]=f,dep[x]=dep[f]+1,siz[x]=1;
for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=f){
dis[u]=dis[x]+w[i>>1],dfs1(u,x),go[i>>1]=u;
if(siz[u]>siz[son[x]]) son[x]=u;
siz[x]+=siz[u];
}
}
void dfs2(int x,int topf){
top[x]=topf,dfn[x]=++dfn[0],id[dfn[0]]=x;
if(!son[x]) return;
dfs2(son[x],topf);
for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=fa[x] and u!=son[x]) dfs2(u,u);
}
inline int LCA(int x,int y){
while(top[x]!=top[y]) dep[top[x]]>dep[top[y]]?(x=fa[top[x]]):(y=fa[top[y]]);
return dep[x]<dep[y]?x:y;
}
#define ls (ro<<1)
#define rs (ro<<1|1)
#define mid ((l+r)>>1)
namespace S{
long long c[maxn];
inline void upd(int x,long long k){for(;x<=n;x+=x&-x) c[x]+=k;}
inline long long query(int x){long long ans=dis[id[x]];for(;x;x-=x&-x) ans+=c[x];return ans;}
inline void update(int x,int y,long long w){upd(x,w),upd(y+1,-w);}
}
inline long long Dis(pair<int,int> a){return S::query(dfn[a.first])+S::query(dfn[a.second])-2*S::query(dfn[LCA(a.first,a.second)]);}
namespace T{
pair<int,int> e[maxn<<2];
inline pair<int,int> merge(const pair<int,int>& a,const pair<int,int>& b){
pair<int,int> p[6]={a,b,make_pair(a.first,b.first),make_pair(a.first,b.second),make_pair(a.second,b.first),make_pair(a.second,b.second)};
long long dis[6];
for(int i=0;i<6;i++) dis[i]=Dis(p[i]);
return p[max_element(dis,dis+6)-dis];
}
void build(int ro=1,int l=1,int r=n){
if(l==r) return e[ro]=make_pair(id[l],id[l]),void();
build(ls,l,mid),build(rs,mid+1,r);
e[ro]=merge(e[ls],e[rs]);
}
void update(int x,int y,int ro=1,int l=1,int r=n){
if(x==l and y==r) return;
if(y<=mid) update(x,y,ls,l,mid);
else if(x>mid) update(x,y,rs,mid+1,r);
else update(x,mid,ls,l,mid),update(mid+1,y,rs,mid+1,r);
e[ro]=merge(e[ls],e[rs]);
}
}
#undef ls
#undef rs
#undef mid
inline void work(){
n=read(),q=read(),W=read();
for(int i=1;i<n;i++) addedge();
dfs1(1,0),dfs2(1,1);
T::build();
long long ans=0;
while(q--){
int e=(read()+ans)%(n-1)+1;
long long v=(read()+ans)%W;
S::update(dfn[go[e]],dfn[go[e]]+siz[go[e]]-1,v-w[e]),w[e]=v;
T::update(dfn[go[e]],dfn[go[e]]+siz[go[e]]-1);
printf("%lld\n",ans=Dis(T::e[1]));
}
}
}
signed main(){
star::work();
return 0;
}
|
